package capper;

//import java.awt.Event;
//import java.beans.EventHandler;
//import java.util.Random;
//import java.util.Vector;

class PriorityEvent {
    public int priority;
    public int data;

    public PriorityEvent(int newPriority, int newData) {
        priority = newPriority;
        data = newData;
    }

    public boolean lessThan(PriorityEvent rh) {
        return priority < rh.priority;
    }
}

class PriorityHeap {
    public PriorityHeap() {
        eventHeap = new PriorityEvent[1];
        eventHeap[0] = null;
        currentTail = 0;
    }

    // Expand the array to be another layer deeper
    // curentTail remains the same
    private void resizeArray() {
    	// Fill a new array with the old one's values, null everything else
    	PriorityEvent[] tempHeap = new PriorityEvent[eventHeap.length * 2 + 1];
        for (int i = 0; i < tempHeap.length; i++) {
        	if (i < eventHeap.length && eventHeap[i] != null) {
        		tempHeap[i] = eventHeap[i];
        	} else {
        		tempHeap[i] = null;
        	}
        }
        
        eventHeap = tempHeap;
    }
    
    private void printHeap() {
    	String buffer = "";
    	int counter = 1;
    	for (int i = 0; i < eventHeap.length; i++) {
    		if (i == counter - 1) {
    			counter = counter << 1;
    			buffer += "\n";
    		}
    		if (eventHeap[i] != null) {
    			buffer += String.format("[%1$02d:%2$02d] ", eventHeap[i].priority, eventHeap[i].data);
    		} else {
    			buffer += "[xx:xx] ";
    		}
    	}
    	System.out.print("Heap contents:" + buffer + "\n");
    }
    
    public void enqueue(int newPriority, int newData) {
    	PriorityEvent newEvent = new PriorityEvent(newPriority, newData);
    	System.out.print("Adding element " + String.format("[%1$02d:%2$02d]", newPriority, newData) + " at index " + Integer.toString(currentTail) + '\n');
    	
        // Ensure that there is an empty leaf
    	if (isFull()) {
    		resizeArray();
    	}
    	
        // Parent node of the first empty node
    	int index = currentTail;
        int parent = currentTail / 2;
        // Verify space exists and add the new event to the end of the array
        
        eventHeap[currentTail] = newEvent;
        ++currentTail;
        
        // While the event is higher priority than its parent in the heap (sift up)
        while (index > 0 && eventHeap[index].lessThan(eventHeap[parent])) {
            // Swap the new event into its parent
            PriorityEvent temp = eventHeap[parent];
            eventHeap[parent] = eventHeap[index];
            // Swap the parent into the old slot
            eventHeap[index] = temp;
            index = parent;
            parent = index / 2;
        }
        
        printHeap();
    }

    private void heapify(int rootIndex) {
        int left = 2 * rootIndex + 1;
        int right = 2 * rootIndex + 2;
        int least = rootIndex;

        // Check for higher priority left leaf
        if (eventHeap.length > left && eventHeap[left] != null && eventHeap[left].lessThan(eventHeap[rootIndex])) {
            least = left;
        }
        // Check for higher priority right leaf
        if (eventHeap.length > right && eventHeap[right] != null && eventHeap[right].lessThan(eventHeap[least])) {
            least = right;
        }
        // Swap higher priority leaf with root if necessary
        if (least != rootIndex) {
            PriorityEvent temp = eventHeap[least];
            eventHeap[least] =  eventHeap[rootIndex];
            eventHeap[rootIndex] = temp;
            heapify(least);
        }
    }

    public void dequeue() {
    	System.out.print("Removing root, sifting element at index " + Integer.toString(currentTail - 1) + '\n');
    	
    	if (isEmpty()) {
    		return;
    	}
    	
        // Remove the tip
        eventHeap[0] = null;

     // If there was more than 1 element, heapify
        currentTail--;
        if (currentTail > 0) {
        	eventHeap[0] = eventHeap[currentTail];
        	eventHeap[currentTail] = null;
        	heapify(0);
        }
        
        printHeap();
    }

    // If the tail is zero, there are no elements in the heap
    public boolean isEmpty() {
        return (currentTail == 0 && eventHeap[0] == null);
    }
    
    public boolean isFull() {
    	return (currentTail >= eventHeap.length);
    }

    // Returns the highest priority event's value, -1 otherwise
    public int topPriority() {
        if (!isEmpty()) {
            return eventHeap[0].priority;
        } else {
            return -1;
        }
    }

    // Returns the highest priority event's data, -1 otherwise
    public int topData() {
    	if (!isEmpty()) {
            return eventHeap[0].data;
        } else {
            return -1;
        }
    }

//    public int getSize() {
//        //return eventHeap.size();
//    	return eventHeap.length;
//    }
    
    public int getTail() {
    	return currentTail;
    }
    
    //private Vector<PriorityEvent> eventHeap;
    private PriorityEvent[] eventHeap;
    // Actually one after the last element
    int currentTail;
}